<?
// <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
include_once "prerequisite.php";

/**
 * Extract entity set with trie
 *
 * @param $token_array 
 *            Tokens are the smallest units for dictionary matching. 
 *            ex) $token_array = tokenize_string($query_text);
 *
 * @param $trie
 *			  The trie is based on an ordered tree data structure with entity tokens as nodes.
 *            ex) $trie = make_trie(array('s1 s2'=>true, 's1 s3'=>true), array());
 *
 * @param $option
 *            verbose : display debug message
 *            max_candidate_length : max length of candidate entity
 *            max_candidate_ref : max number of candidate entity reference
 *            max_apriori_level : max level of apriori step
 *            max_apriori_candidate : max candidate entity per each step
 *            support_uniqueness : EMS are guaranteed to be unique
 */
function extract_entity_mention_set(&$token_array, &$trie, $option = array())
{
	if ( !isset($option['verbose']) ) $option['verbose'] = false;
	if ( !isset($option['max_candidate_length']) ) $option['max_candidate_length'] = 16;			
	if ( !isset($option['max_candidate_ref']) ) $option['max_candidate_ref'] = 128; 			
	if ( !isset($option['max_apriori_level']) ) $option['max_apriori_level'] = 12;		
	if ( !isset($option['max_apriori_candidate']) ) $option['max_apriori_candidate'] = 32; 	
	if ( !isset($option['support_uniqueness']) ) $option['support_uniqueness'] = true; 	
	if ( !isset($option['allowed_coordinator']) ) {
		foreach ( array('and','or','but','either','nor','versus','vs','neither','yet','&',',') as $cc ) {
			$option['allowed_coordinator'][$cc] = true;
			if ( $cc != ',' && $cc != '&' ) $option['allowed_coordinator'][", ".$cc] = true;
		}
	}
	if ( !isset($option['nnp_mode']) ) $option['nnp_mode'] = false; 
	
	$coordinator_list = ems_find_coordinator($token_array, $option);
	$candidate_entity_list = ems_find_candidate_entity($token_array, $trie, $coordinator_list, $option);
	$candidate_entity_list = ems_remove_sub_candidate_entity($candidate_entity_list, $option);
	$connected_candidate_entities_array = ems_find_connected_candidate_entities($candidate_entity_list, $coordinator_list, $option);

	$confidence_list = array();
	$discard_cutoff_list = array();
	$verbose_list = array();
	$statistics_list = array('optimize_pos'=>0, 'optimize_neg'=>0, 'connected'=>array());
	foreach ( $connected_candidate_entities_array as $connected_candidate_entities ) {

		$optimistic_entity_mention_set_list = array();
		$invalid_combination_array = array();

		$support_score_list = array();
		$discard_list = array();
		
		$connected_id = ems_make_entity_mention_set_id($connected_candidate_entities);
		$verbose_list[$connected_id] = array();
		$statistics_list['connected'][$connected_id] = array(
			'connected'=>count($connected_candidate_entities), 
			'continuous'=>0,
			'discontinuous'=>0,
			'combination_pos'=>0,
			'combination_neg'=>0,
			'discard'=>0,
			'support_pos'=>0,
			'support_neg'=>0,
			'support_neg_plus'=>0,
			'support_neg_ast'=>0,
			'support_neg_subset'=>0,
			'support_neg_uniqueness'=>0,
			'confidence_pos'=>0,
			'confidence_neg'=>0
		);

		// init set
		foreach ( $connected_candidate_entities as $candidate_entity_id => $candidate_entity ) {
			$optimistic_entity_mention_set_list[0][$candidate_entity_id] = array($candidate_entity_id=>$candidate_entity);
			$support_score_list[0][$candidate_entity_id] = count($candidate_entity['matched_token_array'])/($candidate_entity['gap_cnt']+1);
			if ( !$candidate_entity['gap_cnt'] ) {
				$verbose_list[$connected_id][0][$candidate_entity_id]['result_combination']['pass'] = true;
				$verbose_list[$connected_id][0][$candidate_entity_id]['result_support']['pass'] = true;
				$verbose_list[$connected_id][0][$candidate_entity_id]['result_confidence']['pass'] = true;
				$confidence_list[$candidate_entity_id]['pattern'] = "U";
				$confidence_list[$candidate_entity_id]['entity_mention_set'] = array($candidate_entity_id=>$candidate_entity);
				$statistics_list['connected'][$connected_id]['continuous']++;
				$statistics_list['connected'][$connected_id]['confidence_pos']++;
			} else {
				$verbose_list[$connected_id][0][$candidate_entity_id]['result_combination']['pass'] = true;
				$verbose_list[$connected_id][0][$candidate_entity_id]['result_support']['pass'] = true;
				$verbose_list[$connected_id][0][$candidate_entity_id]['result_confidence']['pass'] = false;
				$statistics_list['connected'][$connected_id]['discontinuous']++;
				$statistics_list['connected'][$connected_id]['confidence_neg']++;
			}
			$statistics_list['connected'][$connected_id]['combination_pos']++;
		}

		// combined set
		$connected_size = count($connected_candidate_entities);
		for ( $i = 1 ; $i < $option['max_apriori_level'] && $i < $connected_size ; $i++ ) {
			
			if ( count($optimistic_entity_mention_set_list[$i-1]) == 0 ) break;
			if ( count($optimistic_entity_mention_set_list[$i-1]) > $option['max_apriori_candidate'] ) {
				arsort($support_score_list[$i-1]);
				$cnt = 0;
				$discard_cutoff = 0.0;
				foreach ( $support_score_list[$i-1] as $optimistic_entity_mention_set_id => $score ) {
					$cnt++;
					if ( $cnt > $option['max_apriori_candidate'] ) {
						if ( $discard_cutoff == 0.0 ) $discard_cutoff = $score;
						$discard_list[$i-1][$optimistic_entity_mention_set_id] = true;
						$verbose_list[$connected_id][$i-1][$optimistic_entity_mention_set_id]['discarded'] = true;
						$invalid_combination_array[] = explode("|", $optimistic_entity_mention_set_id);
					}
				}
				$statistics_list['connected'][$connected_id]['discard'] += $cnt-$option['max_apriori_candidate'];
				$discard_cutoff_list[$connected_id][$i-1] = $discard_cutoff;
			}
   
			$verbose_list[$connected_id][$i] = array();
			foreach ( $optimistic_entity_mention_set_list[$i-1] as $optimistic_entity_mention_set_id => $optimistic_entity_mention_set ) {
				$last_idx = end(array_keys($optimistic_entity_mention_set));
				if ( $discard_list[$i-1][$optimistic_entity_mention_set_id] ) continue;

				foreach ( $connected_candidate_entities as $candidate_entity_id => $candidate_entity ) {
					if ( $candidate_entity_id <= $last_idx ) continue;
					
					$candidate_entity_mention_set = $optimistic_entity_mention_set;
					$candidate_entity_mention_set[$candidate_entity_id] = $candidate_entity;
					$candidate_entity_mention_set_id = ems_make_entity_mention_set_id($candidate_entity_mention_set);
					$verbose_list[$connected_id][$i][$candidate_entity_mention_set_id] = array();
						
					// filter invalid subset
					$pass = true;
					foreach ( $invalid_combination_array as $idx_arr ) {
						$found = true;
						foreach ( $idx_arr as $idx ) {
							if ( !$candidate_entity_mention_set[$idx] ) {
								$found = false;
								break;
							}
						}
						if ( $found ) {
							$pass = false;
							break;
						}
					}
					$verbose_list[$connected_id][$i][$candidate_entity_mention_set_id]['result_combination']['pass'] = $pass;
					if ( $pass ) {
						$statistics_list['connected'][$connected_id]['combination_pos']++;
					} else {
						$statistics_list['connected'][$connected_id]['combination_neg']++;
						continue;
					}

					$esem_list = ems_make_esem_list($candidate_entity_mention_set);
					$verbose_list[$connected_id][$i][$candidate_entity_mention_set_id]['pattern'] = $esem_list['pattern'];
						
					// check support
					$result_support = ems_verify_support($token_array, $coordinator_list, $candidate_entity_mention_set, $esem_list, $option);
					$verbose_list[$connected_id][$i][$candidate_entity_mention_set_id]['result_support'] = $result_support;
					if ( $result_support['pass'] ) {
						$statistics_list['connected'][$connected_id]['support_pos']++;
					} else {
						$invalid_combination_array[] = array_keys($candidate_entity_mention_set);
						$statistics_list['connected'][$connected_id]['support_neg']++;
						if ( !$result_support['pass_plus'] ) $statistics_list['connected'][$connected_id]['support_neg_plus']++;
						if ( !$result_support['pass_ast'] ) $statistics_list['connected'][$connected_id]['support_neg_ast']++;
						if ( !$result_support['pass_subset'] ) $statistics_list['connected'][$connected_id]['support_neg_subset']++;
						if ( !$result_support['pass_uniqueness'] ) $statistics_list['connected'][$connected_id]['support_neg_uniqueness']++;
						continue;
					}
					$support_score_list[$i][$candidate_entity_mention_set_id] = $result_support['support_score']; 

					// check confidence
					$result_confidence = ems_verify_confidence($token_array, $coordinator_list, $candidate_entity_mention_set, $esem_list, $option);
					$verbose_list[$connected_id][$i][$candidate_entity_mention_set_id]['result_confidence'] = $result_confidence;
						
					if ( $result_confidence['pass'] ) {
						$confidence_list[$candidate_entity_mention_set_id]['pattern'] = $esem_list['pattern'];
						$confidence_list[$candidate_entity_mention_set_id]['entity_mention_set'] = $candidate_entity_mention_set;
						$confidence_list[$candidate_entity_mention_set_id]['connected_size'] = $connected_size;
						$statistics_list['connected'][$connected_id]['confidence_pos']++;
					} else {
						$statistics_list['connected'][$connected_id]['confidence_neg']++;
					}
					$optimistic_entity_mention_set_list[$i][$candidate_entity_mention_set_id] = $candidate_entity_mention_set;
				}
			}
		}
	}
	
	if ( $option['verbose'] ) {
		echo "
<h3>Find semantically valid EMSs</h3>";
		foreach ( $verbose_list as $connected_id => $connected_id_val ) {

			echo "
<p><u>conntected id : $connected_id</u></p>";
				
			foreach ( $connected_id_val as $i => $i_val ) {
				$print_i = sprintf("%d", $i);
				$print_cutoff = "";
				if ( $discard_cutoff_list[$connected_id][$i] ) $print_cutoff = sprintf("(cutoff: %s)", number_format($discard_cutoff_list[$connected_id][$i], 3));
				echo "
<p>i:$print_i $print_cutoff</p>
<ul>";
				foreach ( $i_val as $candidate_entity_mention_set_id => $candidate_entity_mention_set_val ) {

					$print_score = $candidate_entity_mention_set_val['result_support']['support_score'];
					
					$fail_support = "";
					if ( !$candidate_entity_mention_set_val['result_support']['pass_plus'] ) $fail_support .= " plus ";
					if ( !$candidate_entity_mention_set_val['result_support']['pass_ast'] ) $fail_support .= " ast ";
					if ( !$candidate_entity_mention_set_val['result_support']['pass_uniqueness'] ) $fail_support .= " uniqueness ";
					
					$fail_confidence = "";
					if ( !$candidate_entity_mention_set_val['result_confidence']['pass_es'] ) $fail_confidence .= " es ";
					if ( !$candidate_entity_mention_set_val['result_confidence']['pass_ese'] ) $fail_confidence .= " ese ";
					
					$print_fail = "";
					if ( !$candidate_entity_mention_set_val['result_combination']['pass'] ) $print_fail .= "fail at combination";
					else if ( !$candidate_entity_mention_set_val['result_support']['pass'] ) $print_fail .= "fail at support ($fail_support)";
					else if ( $candidate_entity_mention_set_val['result_confidence']['pass'] ) $print_fail .= "<strong>confidence</strong> (pattern:{$candidate_entity_mention_set_val['pattern']}, score:{$print_score})";
					else if ( $candidate_entity_mention_set_val['discarded'] ) $print_fail .= sprintf("discard (%s)", number_format($candidate_entity_mention_set_val['result_support']['support_score'], 3));
					else $print_fail .= "pass (score:{$print_score})";
						
					$print_detail = "";
					if ( $candidate_entity_mention_set_val['result_confidence']['pass'] ) {
						$print_detail .= "
    <ul>";
						foreach ( $confidence_list[$candidate_entity_mention_set_id]['entity_mention_set'] as $candidate_entity_id => $candidate_entity ) {
							$print_detail .= "
      <li>#{$candidate_entity_id} : {$candidate_entity['matched_string']}</li>";
						}
						$print_detail .= "
    </ul>";
					}

					echo "
  <li>[$candidate_entity_mention_set_id] : $print_fail $print_detail</li>";
				}
				echo "
</ul>";				
			}
		}
	}

	$key_array = array();
	foreach ( $confidence_list as $candidate_entity_mention_set_id => $candidate_entity_mention_set_id_val ) {
		$cnt_es_word = 0;
		$cnt_continous = 0;
		$prev_pos = -1;
		foreach ( $candidate_entity_mention_set_id_val['entity_mention_set'] as $candidate_entity_id => $candidate_entity ) {
			foreach ( $candidate_entity['matched_token_array'] as $pos ) {
				$cnt_es_word++;
				if ( $prev_pos != -1 ) {
					if ( $prev_pos + 1 == $pos ) {
						$cnt_continuous++;
					}
				}
				$prev_pos = $pos;
			}
		}
		$key_array[$cnt_es_word][$cnt_continous][] = $candidate_entity_mention_set_id;
	}

	$sorted_array = array();
	krsort($key_array);
	foreach($key_array as $key1 => $val1) {
		krsort($val1);
		foreach($val1 as $key2 => $val2) {
			$sorted_array = array_merge($sorted_array, $val2);
		}
	}

	if ( $option['verbose'] ) echo "
<h3>Find author's EMS</h3>
<table border='0' cellpadding='3' cellspacing='1' class='simple_table'>
  <tr>
    <td>rank</td>
    <td>entity_mention_set_id</td>
    <td>string</td>
    <td>entity</td>
    <td>status</td>
  </tr>";

	$optimized_entity_mention_set_list = array();
	$mask_array = array();
	$rank = 0;
	foreach ( $sorted_array as $candidate_entity_mention_set_id ) {
		$rank++;
		
		$candidate_entity_mention_set = $confidence_list[$candidate_entity_mention_set_id]['entity_mention_set'];
		$pattern = $confidence_list[$candidate_entity_mention_set_id]['pattern'];
		$connected_size = $confidence_list[$candidate_entity_mention_set_id]['connected_size'];

		$print_entity = "";
		$pass = true;
		$lpos = -1;
		$rpos = -1;
		foreach ( $candidate_entity_mention_set as $candidate_entity_id => $candidate_entity ) {
			foreach ( $candidate_entity['matched_token_array'] as $pos ) {
				if ( $lpos == -1 || $lpos > $pos ) $lpos = $pos;
				if ( $rpos == -1 || $rpos < $pos ) $rpos = $pos;
				if ( $mask_array[$pos] ) $pass = false;
			}
			if ( $print_entity ) $print_entity .= ", ";
			$print_entity .= ems_make_matched_string($token_array, $candidate_entity['matched_token_array']);
		}

		$print_string = "";
		for ( $i = $lpos ; $i <= $rpos ; $i++ ) {
			if ( $print_string ) $print_string .= " ";
			$print_string .= $token_array[$i]['str'];
		}
		
		$ncs = "";
		$n = $rpos-$lpos+1;
		$c = 0;
		$is_coordinator = false;
		for ( $i = $lpos ; $i <= $rpos ; $i++ ) {
			if ( $is_coordinator == false && $coordinator_list[$i]) $c++;
			if ( $coordinator_list[$i] ) $is_coordinator = true;
			else $is_coordinator = false;
		}
		$s = $connected_size;
		$ncs = "$n|$c|$s";

		$print_status = "filtered";
		if ( $pass ) {
			foreach ( $candidate_entity_mention_set as $candidate_entity_id => $candidate_entity ) {
				foreach ( $candidate_entity['matched_token_array'] as $pos ) {
					$mask_array[$pos] = true;
				}
			}
			$optimized_entity_mention_set_list[$candidate_entity_mention_set_id] = array('entity_mention_set'=>$candidate_entity_mention_set, 'pattern'=>$pattern, 'ltoken'=>$lpos, 'rtoken'=>$rpos, 'ncs'=>$ncs);
			$print_status = "<strong>found</strong>";
			if ( count($candidate_entity_mention_set) > 1 ) $statistics_list['optimize_pos']++;
		} else {
			$statistics_list['optimize_neg']++;
		}

		if ( $option['verbose'] ) echo "
  <tr>
    <td valign='top'>#{$rank}</td>
    <td valign='top'>{$candidate_entity_mention_set_id}</td>
    <td valign='top'>{$print_string}</td>
    <td valign='top'>{$print_entity}</td>
    <td valign='top'>{$print_status}</td>
  </tr>";		
	}
	if ( $option['verbose'] ) echo "
</table>";

	if ( $option['statistics'] ) {
		return $statistics_list;
	}

	if ( $option['nnp_mode'] ) {
		$pos_entity_mention_set_id_list = array();
		foreach ( $optimized_entity_mention_set_list as $entity_mention_set_id => $entity_mention_set_val ) {
			$ltoken = $entity_mention_set_val['ltoken'];
			$pos_entity_mention_set_id_list[$ltoken] = $entity_mention_set_id;
		}
		
		$sum_plus_array = array();
		$cur_plus_array = array();
		for ( $i = 0 ; $i < count($token_array) ; $i++ ) {
		
			if ( $pos_entity_mention_set_id_list[$i] ) {
				$entity_mention_set_id = $pos_entity_mention_set_id_list[$i];
				$add_plus_array = array();
				foreach ( $optimized_entity_mention_set_list[$entity_mention_set_id]['entity_mention_set'] as $idx => $match ) {
					$add_plus_array[] = $match['matched_token_array'];
				}
				
				if ( count($cur_plus_array) == 0 ) {
					$cur_plus_array = $add_plus_array;
				} else {
					if ( count($cur_plus_array) == 1 ) {
						$prev_cur_plus_array = $cur_plus_array;
						$cur_plus_array = array();
						foreach ( $prev_cur_plus_array as $prev_match ) {
							foreach ( $add_plus_array as $add_match ) {
								$cur_plus_array[] = array_merge($prev_match, $add_match);
							}
						}
					} else {
						
						$last_idx = count($cur_plus_array)-1;
						$cur_plus_array[$last_idx] = array_merge($cur_plus_array[$last_idx], $add_plus_array[0]);
						for ( $j = 1 ; $j < count($add_plus_array) ; $j++ ) {
							$cur_plus_array[] = $add_plus_array[$j];
						}
					}
				}
				$i = $optimized_entity_mention_set_list[$entity_mention_set_id]['rtoken'];

			} else {
				
				if ( $coordinator_list[$i] ) {
					if ( count($cur_plus_array) ) {
						$sum_plus_array = array_merge($sum_plus_array, $cur_plus_array);
					}
					$cur_plus_array = array();
					
				} else {
					if ( count($cur_plus_array) == 0 ) {
						$cur_plus_array[0][] = $i;
					} else {
						for ( $j = 0 ; $j < count($cur_plus_array) ; $j++ ) {
							$cur_plus_array[$j][] = $i;
						}
					}
				}
			}
		}
		if ( count($cur_plus_array) ) {
			$sum_plus_array = array_merge($sum_plus_array, $cur_plus_array);
		}
		return $sum_plus_array;
	}
	
	return $optimized_entity_mention_set_list;
}

function ems_find_coordinator(&$token_array, $option = array())
{
	$allowed_coordinator = $option['allowed_coordinator'];
	$allowed_coordinator_word_list = array();
	foreach ( $allowed_coordinator as $str => $val ) {
		if ( !$val ) continue; 
		foreach ( explode(" ", $str) as $word ) {
			$allowed_coordinator_word_list[$word] = true;
		}
	}

	$coordinator_list = array();
	for ( $i = 0 ; $i < count($token_array) ; $i++ ) {
		$str = $token_array[$i]['str'];
		if ( $allowed_coordinator_word_list[$str] ) $coordinator_list[$i] = true;
	}
	return $coordinator_list;
}


function ems_find_candidate_entity(&$token_array, &$trie, $coordinator_list, $option = array())
{
	$verbose_list_array = array();

	$ref_array = array();		// trie reference
	$tpos_array = array();		// token position array
	$candidate_entity_list = array();		// output

	$ref_array[] =& $trie;
	$tpos_array[] = array();
	$unused_list = array();

	$ref_count = 1;
	$word_cnt = count($token_array);
	for ( $i = 0 ; $i < $word_cnt ; $i++ ) {
		$str = $token_array[$i]['str'];
		$tag = $token_array[$i]['tag'];

		if ( $tag == "_cmd_init_ref" ) {
			for ( $j = 1 ; $j < $ref_count ; $j++ ) $unused_list[$j] = true;
		}

		$prev_ref_count = $ref_count;
		$verbose_list = array('i'=>$i);
		for ( $j = 0 ; $j < $prev_ref_count && $j < $option['max_candidate_ref'] ; $j++ ) {

			if ( $unused_list[$j] ) continue;

			if ( $i >= $tpos_array[$j][0] + $option['max_candidate_length'] && $j != 0 ) {
				$unused_list[$j] = true;
				continue;
			}

			if ( !isset($ref_array[$j][$str]) ) {
				if  ( !isset($ref_array[$j][$tag]) ) continue;
				$idx = $tag;
			} else {
				$idx = $str;
			}

			$matched_token_array = $tpos_array[$j];
			$matched_token_array[] = $i;
				
			$matched_str = "";
			foreach ( $matched_token_array as $tpos ) {
				if ( $matched_str ) $matched_str .= " ";
				$matched_str .= $token_array[$tpos]['str'];
			}
			$matched_idx = implode(" ", $matched_token_array);
			$verbose_list = array('i'=>$i, 'ref'=>$j, 'Matched idx'=>$matched_idx, 'Matched string'=>$matched_str);
				
			$cnt_item = count($ref_array[$j][$idx]);	

			if ( isset($ref_array[$j][$idx]['_val']) ) {

				$gap_cnt = 0;
				$gap_length = 0;
				$prev_pos = -1;
				foreach ( $matched_token_array as $pos ) {
					if ( $prev_pos != -1 ) {
						if ( $prev_pos+1 != $pos ) {
							$gap_cnt++;
							$gap_length += $pos-$prev_pos-1;
						}
					} 
					$prev_pos = $pos;
				}
				
				$cnt_match = count($candidate_entity_list);
				$candidate_entity_list[$cnt_match] = array(
					'idx'=>$cnt_match,
					'val'=>$ref_array[$j][$idx]['_val'], 
					'matched_token_array'=>$matched_token_array,
					'matched_string'=>$matched_str,
					'gap_cnt'=>$gap_cnt,
					'gap_length'=>$gap_length);
				$cnt_item--;

				$verbose_list['idx'] = $cnt_match;
				$verbose_list['terminal'] = true;
			}

			if ( $cnt_item > 0 ) {
					
				$verbose_list['nref'] = $ref_count;

				$ref_array[$ref_count] =& $ref_array[$j][$idx];
				$tpos_array[$ref_count] = $matched_token_array;

				$ref_count++;
			}
			$verbose_list_array[] = $verbose_list;
		}
		if ( !isset($verbose_list['ref']) ) {
			if ( !$coordinator_list[$i] ) {
				for ( $j = 1 ; $j < $ref_count ; $j++ ) $unused_list[$j] = true;
			}
			$verbose_list_array[] = $verbose_list;
		}
	}

	if ( $option['verbose'] ) {
		echo "
<h3>Find candidate entities</h3>
<table border='0' cellpadding='3' cellspacing='1' class='simple_table'>
  <tr>
    <td>Token ID</td>
    <td>Token</td>
    <td>Reference<br>
(found-new)</td>
    <td>Matched tokens IDs</td>
    <td>Matched tokens</td>
  </tr>";
		$print_idx_list = array();
		foreach ( $verbose_list_array as $verbose_list ) {
			$i = $verbose_list['i'];
			if ( $print_idx_list[$i] ) {
				$print_i = "&nbsp;";
				$print_str = "&nbsp;";
				$print_tag = "&nbsp;";
			} else {
				$print_i = "#{$i}";
				$print_str = $token_array[$i]['str'];
				$print_tag = $token_array[$i]['tag'];
			}
			$print_ref = "";
			if ( isset($verbose_list['ref']) ) $print_ref = "#{$verbose_list['ref']}";
			$print_nref = "";
			if ( isset($verbose_list['nref']) ) $print_nref = "#{$verbose_list['nref']}";
			$print_matched_idx = $verbose_list['Matched idx'];
			$print_matched_string = $verbose_list['Matched string'];
			if ( isset($verbose_list['idx']) ) $print_matched_string .= " <strong>(#{$verbose_list['idx']})</strong>";
			echo "
  <tr>
    <td valign='top'>{$print_i}</td>
    <td valign='top'>{$print_str}</td>
    <td valign='top'>{$print_ref}-{$print_nref}</td>
    <td valign='top'>{$print_matched_idx}</td>
    <td valign='top'>{$print_matched_string}{$print_match_idx}</td>
  </tr>";
			$print_idx_list[$i] = true;
		}
		echo "
</table>
";		
	}

	return $candidate_entity_list;
}

function ems_remove_sub_candidate_entity($candidate_entity_list, $option)
{
	$verbose_list = array();

	$key_array = array();
	foreach ( $candidate_entity_list as $candidate_entity_id => $candidate_entity ) {
		if ( $candidate_entity['gap_cnt'] > 0 ) continue;
		$len = count($candidate_entity['matched_token_array']);
		$pos2 = $candidate_entity['matched_token_array'][$len-1];
		$key_array[$len][$pos2] = $candidate_entity;
	}

	$passed_list = array();
	$mask_array = array();
	krsort($key_array);
	foreach($key_array as $len => $len_val) {

		krsort($len_val);
		foreach($len_val as $pos2 => $candidate_entity) {

			$pos1 = $candidate_entity['matched_token_array'][0];

			$pass = true;
			for ( $p = $pos1 ; $p <= $pos2 ; $p++ )
			if ( $mask_array[$p] ) $pass = false;
				
			$idx = $candidate_entity['idx'];
			if ( $pass ) {
				$verbose_list[$idx] = array('pass'=>true, 'candidate_entity'=>$candidate_entity);
				$passed_list[$idx] = $candidate_entity;
				for ( $p = $pos1 ; $p <= $pos2 ; $p++ ) $mask_array[$p] = true;
			} else {
				$verbose_list[$idx] = array('pass'=>false, 'candidate_entity'=>$candidate_entity);
			}
		}
	}

	foreach ( $candidate_entity_list as $candidate_entity_id => $candidate_entity ) {
		if ( !$candidate_entity['gap_cnt'] ) continue;
		$passed_list[$candidate_entity_id] = $candidate_entity;
	}
	ksort($passed_list);

	if ( $option['verbose'] ) {
		echo "
<h3>Remove overlapping candidate entities</h3>
<table border='0' cellpadding='3' cellspacing='1' class='simple_table'>
  <tr>
    <td>idx</td>
    <td>tpos array</td>
    <td>string</td>
    <td>exact</td>
    <td>status</td>
    </tr>";
		foreach ( $candidate_entity_list as $candidate_entity_id => $candidate_entity ) {
			$print_tpos = implode(" ", $candidate_entity['matched_token_array']);
			$print_exact = "";
			if ( !$candidate_entity['gap_cnt'] ) $print_exact = "V";
			$print_status = "";
			if ( !$candidate_entity['gap_cnt'] ) {
				if ( !$verbose_list[$candidate_entity_id]['pass'] ) $print_status = "<span class='warning'>removed</span>";
			}
			echo "
  <tr>
    <td valign='top'>#{$candidate_entity_id}</td>
    <td valign='top'>{$print_tpos}</td>
    <td valign='top'>{$candidate_entity['matched_string']}</td>
    <td valign='top' align='center'>{$print_exact}</td>
    <td valign='top'>{$print_status}</td>
    </tr>";
		}
		echo "
</table>
";		
	}

	return $passed_list;
}

function ems_find_connected_candidate_entities($candidate_entity_list, $coordinator_list, $option = array())
{
	$key1_array = array_keys($candidate_entity_list);
	$key2_array = array_keys($candidate_entity_list);

	$node_list = array();
	$adjacency_matrix = array();
	foreach ( $key1_array as $i ) {
		$node_list[$i] = true;
		foreach ( $key2_array as $j ){
			if ( $i >= $j ) continue;
			$set_relation = find_set_relation($candidate_entity_list[$i]['matched_token_array'], $candidate_entity_list[$j]['matched_token_array']);
			if ( !$set_relation['disjoint'] ) {
				$adjacency_matrix[$i][$j] = true;
				$adjacency_matrix[$j][$i] = true;
			} else if ( $set_relation['disjoint'] ) {
				if ( ems_is_disjoint_connected($candidate_entity_list[$i]['matched_token_array'], $candidate_entity_list[$j]['matched_token_array'], $coordinator_list) ) {
					$adjacency_matrix[$i][$j] = true;
					$adjacency_matrix[$j][$i] = true;
				}
			}
		}
	}
	$connected_component_array = find_connected_component($node_list, $adjacency_matrix);

	$connected_i_list = array();
	$connected_candidate_entities_array = array();
	for ( $connected_i = 0 ; $connected_i < count($connected_component_array) ; $connected_i++ ) {
		$connected_component = $connected_component_array[$connected_i];

		$items = array();
		foreach ( $connected_component as $idx ) {
			$items[$idx] = $candidate_entity_list[$idx];
			$connected_i_list[$idx] = $connected_i;
		}
		ksort($items);
		$connected_candidate_entities_array[] = $items;
	}
	
	if ( $option['verbose'] ) {
		
		$print_last_gap = "";
		echo "
<h3>Find candidate entity groups</h3>
<table border='0' cellpadding='3' cellspacing='1' class='simple_table'>
  <tr>
    <td>idx</td>
    <td>tpos array</td>
    <td>string</td>
    <td>connect id</td>
     </tr>";
		foreach ( $candidate_entity_list as $candidate_entity_id => $candidate_entity ) {
			$print_tpos = implode(" ", $candidate_entity['matched_token_array']);
			echo "
  <tr>
    <td valign='top'>#{$candidate_entity_id}</td>
    <td valign='top'>{$print_tpos}</td>
    <td valign='top'>{$candidate_entity['matched_string']}</td>
    <td valign='top'>#{$connected_i_list[$candidate_entity_id]}</td>
    </tr>";
		}
		echo "
</table>
";		
	}	
	return $connected_candidate_entities_array;
}

function ems_is_disjoint_connected($pos_array1, $pos_array2, $coordinator_list)
{
	$array1_l = reset($pos_array1);
	$array1_r = end($pos_array1);
	$array2_l = reset($pos_array2);
	$array2_r = end($pos_array2);

	$pass = true;
	if ( $array1_r < $array2_l ) {
		for ( $i = $array1_r+1 ; $i < $array2_l ; $i++ ) {
			if ( !$coordinator_list[$i] ) $pass = false;
		}
	} else if ( $array2_r < $array1_l ) {
		for ( $i = $array2_r+1 ; $i < $array1_l ; $i++ ) {
			if ( !$coordinator_list[$i] ) $pass = false;
		}
	} else {
		$pass = false;
	}

	return $pass;
}

function ems_make_entity_mention_set_id($entity_mention_set)
{
	ksort($entity_mention_set);
	$id = implode("|", array_keys($entity_mention_set));
	return "$id";
}


function ems_make_esem_list($candidate_entity_mention_set)
{
	$edge_list = array('forward'=>array(), 'backward'=>array());
	$used_word_list = array();
	$psu_lpos_list = array();
	foreach ( $candidate_entity_mention_set as $candidate_entity_id => $candidate_entity ) {
		$prev = -1;
		foreach ( $candidate_entity['matched_token_array'] as $cur ) {
			if ( $prev != -1 ) {
				$edge_list['forward'][$prev][$cur] = true;
				$edge_list['backward'][$cur][$prev] = true;
			}
			$used_word_list[$cur] = true;
			if ( $prev == -1 || $prev + 1 != $cur ) $psu_lpos_list[$cur] = true;
			$prev = $cur;
		}
	}
	foreach ( array_keys($edge_list['forward']) as $k ) ksort($edge_list['forward'][$k]);
	foreach ( array_keys($edge_list['backward']) as $k ) krsort($edge_list['backward'][$k]);
	ksort($used_word_list);

	$boundary_list = array('l'=>array(), 'i'=>array(), 'r'=>array());
	foreach ( $candidate_entity_mention_set as $candidate_entity_id => $candidate_entity ) {
		$cnt_token = count($candidate_entity['matched_token_array']);
		for ( $i = 0 ; $i < $cnt_token ; $i++ ) {
			$pos = $candidate_entity['matched_token_array'][$i];
			if ( $i == 0 && $i == $cnt_token - 1 ) {
				$boundary_list['l'][$pos] = true;
				$boundary_list['r'][$pos] = true;
			} else if ( $i == 0 ) {
				$boundary_list['l'][$pos] = true;
			} else if ( $i == $cnt_token - 1 ) {
				$boundary_list['r'][$pos] = true;
			} else {
				$boundary_list['i'][$pos] = true;
			}
		}
	}

	$redge_list = array();
	foreach ( array('forward','backward') as $dir ) {
		foreach ( $edge_list[$dir] as $s => $s_val ) {
			if ( count($s_val) < 2 ) continue;
			foreach ( $s_val as $d => $d_val ) {
				$redge_list[$dir][$d][$s] = true;
			}
		}
	}

	$psu_list = array();
	$pos_array = array();
	$psu_cnt = 0;
	$prev = -1;
	foreach ( $used_word_list as $cur => $val ) {

		if ( $redge_list['forward'][$cur] && !$redge_list['backward'][$cur] ) {
			if ( count($pos_array) ) {
				foreach ( $pos_array as $pos ) $psu_list[$psu_cnt]['pos_list'][$pos] = true;
				$pos_array = array();
				$psu_cnt++;
			}
			$pos_array[] = $cur;
							
		} else if ( !$redge_list['forward'][$cur] && $redge_list['backward'][$cur] ) {
			if ( count($pos_array) && $psu_lpos_list[$cur] ) {
				foreach ( $pos_array as $pos ) $psu_list[$psu_cnt]['pos_list'][$pos] = true;
				$pos_array = array();
				$psu_cnt++;
			}
			$pos_array[] = $cur;
			foreach ( $pos_array as $pos ) $psu_list[$psu_cnt]['pos_list'][$pos] = true;
			$pos_array = array();
			$psu_cnt++;

		} else if ( $redge_list['forward'][$cur] && $redge_list['backward'][$cur] ) {
			if ( count($pos_array) ) {
				foreach ( $pos_array as $pos ) $psu_list[$psu_cnt]['pos_list'][$pos] = true;
				$pos_array = array();
				$psu_cnt++;
			}
			$pos_array[] = $cur;
			foreach ( $pos_array as $pos ) $psu_list[$psu_cnt]['pos_list'][$pos] = true;
			$pos_array = array();
			$psu_cnt++;
				
		} else if ( $psu_lpos_list[$cur] ) {
			if ( count($pos_array) ) {
				foreach ( $pos_array as $pos ) $psu_list[$psu_cnt]['pos_list'][$pos] = true;
				$pos_array = array();
				$psu_cnt++;
			}
			$pos_array[] = $cur;
				
		} else {
			$pos_array[] = $cur;
		}
		$prev = $cur;
	}
	if ( count($pos_array) ) {
		foreach ( $pos_array as $pos ) $psu_list[$psu_cnt]['pos_list'][$pos] = true;
	}

	$token_psu_list = array();
	foreach ( $psu_list as $psu => $psu_val ) {
		foreach ( $psu_val['pos_list'] as $pos => $val ) {
			$token_psu_list[$pos] = $psu;
		}
	}

	$entity_psu_array = array();
	foreach ( $candidate_entity_mention_set as $candidate_entity_id => $candidate_entity ) {
		$list = array();
		foreach ( $candidate_entity['matched_token_array'] as $pos ) {
			$psu = $token_psu_list[$pos];
			$list[$psu] = true;
		}
		$entity_psu_array[$candidate_entity_id] = array_keys($list);
	}

	$psu_edge_list = array('forward'=>array(), 'backward'=>array());
	$psu_subtoken_list = array('forward'=>array(), 'backward'=>array());
	$psu_boundary_list = array();
	foreach ( $psu_list as $psu => $psu_val ) $psu_list[$psu]['solo'] = true;
	foreach ( $entity_psu_array as $candidate_entity_id => $psu_array ) {
		$cnt_psu = count($psu_array);

		$prev = -1;
		foreach ( $psu_array as $cur ) {
			if ( $prev != -1 ) {
				$psu_edge_list['forward'][$prev][$cur] = true;
				$psu_edge_list['backward'][$cur][$prev] = true;
				$psu_list[$cur]['solo'] = false;
				$psu_list[$prev]['solo'] = false;
			}
			$prev = $cur;
		}

		$prev_array = array();
		for ( $i = 0 ; $i < $cnt_psu ; $i++ ) {
			$cur = $psu_array[$i];
			foreach ( $prev_array as $prev ) $psu_subtoken_list['forward'][$prev][$cur] = true;
			$prev_array[] = $cur;
		}

		$prev_array = array();
		for ( $i = $cnt_psu - 1  ; $i >= 0 ; $i-- ) {
			$cur = $psu_array[$i];
			foreach ( $prev_array as $prev ) $psu_subtoken_list['backward'][$prev][$cur] = true;
			$prev_array[] = $cur;
		}

		for ( $i = 0 ; $i < $cnt_psu ; $i++ ) {
			$psu = $psu_array[$i];
			if ( $i == 0 && $i == $cnt_psu - 1 ) {
				$psu_boundary_list['l'][$psu] = true;
				$psu_boundary_list['r'][$psu] = true;
			} else if ( $i == 0 ) {
				$psu_boundary_list['l'][$psu] = true;
			} else if ( $i == $cnt_token - 1 ) {
				$psu_boundary_list['r'][$psu] = true;
			} else {
				$psu_boundary_list['i'][$psu] = true;
			}
		}

	}
	foreach ( array_keys($psu_edge_list['forward']) as $k ) ksort($psu_edge_list['forward'][$k]);
	foreach ( array_keys($psu_edge_list['backward']) as $k ) krsort($psu_edge_list['backward'][$k]);
	foreach ( array_keys($psu_subtoken_list['forward']) as $k ) ksort($psu_subtoken_list['forward'][$k]);
	foreach ( array_keys($psu_subtoken_list['backward']) as $k ) krsort($psu_subtoken_list['backward'][$k]);

	// psu_parenthesis_list
	$psu_parenthesis_list = array();
	foreach ( $psu_edge_list['forward'] as $ps => $ps_val ) {
		if ( count($ps_val) < 2 ) continue;
		$pd_array = array_keys($ps_val);
		$lpsu = reset($pd_array);
		$rpsu = $rpd = end($pd_array);
		if ( $psu_subtoken_list['forward'][$rpd] ) {
			$spd_array = array_keys($psu_subtoken_list['forward'][$rpd]);
			$rpsu = end($spd_array);
			$prev_p = $rpd;
			foreach ( $spd_array as $p ) {
				$have = true;
				foreach ( $ps_val as $pd => $pd_val ) if ( !$psu_subtoken_list['forward'][$pd][$p] ) $have = false;
				if ( $have ) {
					$rpsu = $prev_p;
					break;
				}
				$prev_p = $p;
			}
		}
		$psu_parenthesis_list[$lpsu][$rpsu] = true;
	}
	foreach ( $psu_edge_list['backward'] as $ps => $ps_val ) {
		if ( count($ps_val) < 2 ) continue;
		$pd_array = array_keys($ps_val);
		$rpsu = reset($pd_array);
		$lpsu = $lpd = end($pd_array);
		if ( $psu_subtoken_list['backward'][$lpd] ) {
			$spd_array = array_keys($psu_subtoken_list['backward'][$lpd]);
			$lpsu = end($spd_array);
			$prev_p = $lpd;
			foreach ( $spd_array as $p ) {
				$have = true;
				foreach ( $ps_val as $pd => $pd_val ) if ( !$psu_subtoken_list['backward'][$pd][$p] ) $have = false;
				if ( $have ) {
					$lpsu = $prev_p;
					break;
				}
				$prev_p = $p;
			}
		}
		$psu_parenthesis_list[$lpsu][$rpsu] = true;
	}

	// plus_list
	$plus_list = array();
	foreach ( $psu_edge_list['forward'] as $ps => $ps_val ) {
		if ( count($ps_val) < 2 ) continue;
		$rpos = -1;
		foreach ( $ps_val as $pd => $pd_val ) {
			$pos_array = array_keys($psu_list[$pd]['pos_list']);
			$lpos = reset($pos_array);
			if ( $rpos != -1 ) $plus_list[$lpos-1] = true;
			$rpos = end($pos_array);
		}
	}
	foreach ( $psu_edge_list['backward'] as $ps => $ps_val ) {
		if ( count($ps_val) < 2 ) continue;
		$lpos = -1;
		foreach ( $ps_val as $pd => $pd_val ) {
			$pos_array = array_keys($psu_list[$pd]['pos_list']);
			$rpos = end($pos_array);
			if ( $lpos != -1 ) $plus_list[$rpos+1] = true;
			$lpos = reset($pos_array);
		}
	}
	$rpos = -1;
	foreach ( $psu_list as $psu => $psu_val ) {
		$pos_array = array_keys($psu_val['pos_list']);
		$lpos = reset($pos_array);
		if ( $psu_boundary_list['l'][$psu] && $rpos != -1 ) $plus_list[$lpos-1] = true;	// 생략없이 나열된 coordinated PSU를 위해
		$rpos = end($pos_array);
	}
	ksort($plus_list);

	// psu_model_list
	$psu_operator_list = array();
	$first = true;
	foreach ( $psu_list as $psu => $val ) {
		$psu_operator_list[$psu] = array('('=>0, ')'=>0, 'left_operator'=>'+');
		if ( $first ) {
			$psu_operator_list[$psu]['left_operator'] = '';
			$first = false;
		}
	}
	foreach ( $psu_parenthesis_list as $lpsu => $lpsu_val ) {
		foreach ( $lpsu_val as $rpsu => $rpsu_val ) {
			$psu_operator_list[$lpsu]['(']++;
			$psu_operator_list[$rpsu][')']++;
		}
	}
	foreach ( $psu_edge_list['forward'] as $ps => $ps_val ) {
		if ( count($ps_val) < 2 ) continue;
		$lpsu = reset(array_keys($ps_val));
		$psu_operator_list[$lpsu]['left_operator'] = '*';
	}
	foreach ( $psu_edge_list['backward'] as $ps => $ps_val ) {
		if ( count($ps_val) < 2 ) continue;
		$rpsu = reset(array_keys($ps_val));
		$psu_operator_list[$rpsu+1]['left_operator'] = '*';
	}
	
	// model_array
	$model_array = array();
	foreach ( $psu_list as $psu => $val ) {
		if ( $psu_operator_list[$psu]['left_operator'] ) $model_array[] = array('type'=>'operator', 'value'=>$psu_operator_list[$psu]['left_operator']);
		for ( $i = 0 ; $i < $psu_operator_list[$psu]['('] ; $i++ ) $model_array[] = array('type'=>'operator', 'value'=>'(');
		$model_array[] = array('type'=>'psu', 'value'=>$psu);
		for ( $i = 0 ; $i < $psu_operator_list[$psu][')'] ; $i++ ) $model_array[] = array('type'=>'operator', 'value'=>')');
	}
	
	// pattern, string
	$pattern = "";
	$string = "";
	foreach ( $model_array as $model ) {
		if ( strlen($pattern) ) $pattern .= " ";
		if ( strlen($string) ) $string .= " ";
		if ( $model['type'] == 'operator' ) {
			$pattern .= $model['value']; 
			$string .= $model['value']; 
		} else if ( $model['type'] == 'psu' ) {
			$pattern .= "U";
			$string .= $model['value'];
		} 
	}
	
	return array(
		'edge_list'=>$edge_list, 
		'boundary_list'=>$boundary_list, 
		'used_word_list'=>$used_word_list, 
		'redge_list'=>$redge_list, 
		'psu_list'=>$psu_list, 
		'token_psu_list'=>$token_psu_list, 
		'entity_psu_array'=>$entity_psu_array, 
		'psu_edge_list'=>$psu_edge_list, 
		'psu_subtoken_list'=>$psu_subtoken_list, 
		'psu_boundary_list'=>$psu_boundary_list, 
		'psu_parenthesis_list'=>$psu_parenthesis_list, 
		'plus_list'=>$plus_list, 
		'psu_operator_list'=>$psu_operator_list, 
		'model_array'=>$model_array, 
		'pattern'=>$pattern, 
		'string'=>$string 
	);
}


function ems_verify_support(&$token_array, $coordinator_list, $candidate_entity_mention_set, $esem_list, $option = array())
{
	$edge_list = $esem_list['edge_list'];
	$used_word_list = $esem_list['used_word_list'];
	$boundary_list = $esem_list['boundary_list'];
	$plus_list = $esem_list['plus_list'];
	
	$pass_plus = true;
	foreach ( $plus_list as $pos => $val ) {
		if ( !$coordinator_list[$pos] ) $pass_plus = false;
	}

	$pass_ast = true;
	$ast_list = array();
	foreach ( $candidate_entity_mention_set as $candidate_entity_idx => $candidate_entity ) {
		$cnt_token = count($candidate_entity['matched_token_array']);
		for ( $i = 0 ; $i < $cnt_token ; $i++ ) {
			$pos = $candidate_entity['matched_token_array'][$i];
			if ( $i != 0 ) $ast_list['l'][$pos] = true;
			if ( $i != $cnt_token - 1 ) $ast_list['r'][$pos] = true;
		}
	}
	foreach ( $candidate_entity_mention_set as $candidate_entity_idx => $candidate_entity ) {
		$cnt_token = count($candidate_entity['matched_token_array']);
		for ( $i = 0 ; $i < $cnt_token ; $i++ ) {
			$pos = $candidate_entity['matched_token_array'][$i];
			if ( $ast_list['l'][$pos] && $i == 0 ) $pass_ast = false;
			if ( $ast_list['r'][$pos] && $i == $cnt_token - 1 ) $pass_ast = false;
		}
	}
	
	$pass_subset = true;
	$tmp_candidate_entity_mention_set = $candidate_entity_mention_set;
	foreach ( $candidate_entity_mention_set as $candidate_entity_idx1 => $candidate_entity1 ) {
		$tpos1_list = array();
		foreach ( $candidate_entity1['matched_token_array'] as $pos1 ) $tpos1_list[$pos1] = true;
		foreach ( $tmp_candidate_entity_mention_set as $candidate_entity_idx2 => $candidate_entity2 ) {
			if ( $candidate_entity_idx1 == $candidate_entity_idx2 ) continue;

			$all = 0;
			$match = 0;
			foreach ( $candidate_entity2['matched_token_array'] as $pos2 ) {
				if ( $tpos1_list[$pos2] ) $match++;
				$all++;
			}
			if ( $match == $all ) $pass_subset = false;
		}
	}
	
	// uniqueness
	$pass_uniqueness = true;
	if ( $option['support_uniqueness'] ) {
		$str_list = array();
		foreach ( $candidate_entity_mention_set as $candidate_entity_idx => $candidate_entity ) {
			$str = $candidate_entity['matched_string'];
			if ( $str_list[$str] ) {
				$pass_uniqueness = false;
				break;
			} else {
				$str_list[$str] = true;
			}
		}
	}
	
	// support score
	$allowed_edge_list = array();
	foreach ( $edge_list['forward'] as $s => $s_val ) {
		if ( count($s_val) < 2 ) continue;
		foreach ( $s_val as $d => $d_val ) $allowed_edge_list[$s][$d] = true;
	}
	foreach ( $edge_list['backward'] as $s => $s_val ) {
		if ( count($s_val) < 2 ) continue;
		foreach ( $s_val as $d => $d_val ) $allowed_edge_list[$d][$s] = true;
	}
	$token_cnt = 0;
	$gap_cnt = 0;
	$gap_length = 0;
	foreach ( $candidate_entity_mention_set as $candidate_entity_id => $candidate_entity ) {
		$prev_pos = -1;
		foreach ( $candidate_entity['matched_token_array'] as $pos ) {
			$token_cnt++;
			if ( $prev_pos != -1 ) {
				if ( $prev_pos+1 != $pos && !$allowed_edge_list[$prev_pos][$pos] ) {
					$gap_cnt++;
					$gap_length += $pos-$prev_pos-1;
				}
			} 
			$prev_pos = $pos;
		}
	}
	return array('pass'=>$pass_plus && $pass_ast && $pass_subset && $pass_uniqueness, 'pass_plus'=>$pass_plus, 'pass_ast'=>$pass_ast, 'pass_subset'=>$pass_subset, 'pass_uniqueness'=>$pass_uniqueness, 'support_score'=>$token_cnt/($gap_cnt+1));
}


function ems_verify_confidence(&$token_array, $coordinator_list, $candidate_entity_mention_set, $esem_list, $option = array())
{
	$allowed_coordinator = $option['allowed_coordinator'];
	$entity_psu_array = $esem_list['entity_psu_array'];
	$model_array = $esem_list['model_array'];
	$plus_list = $esem_list['plus_list'];
	$used_word_list = $esem_list['used_word_list'];

	$original_es_array = array();
	foreach ( $entity_psu_array as $candidate_entity_id => $psu_array ) {
		$original_es_array[] = implode("|", $psu_array);
	}

	$idx = 0;
	$depth = 0;
	$expanded_es_array = ems_expand_esem($model_array, $idx, $depth);

	sort($original_es_array);
	sort($expanded_es_array);

	$pass_es = true;
	$cnt_original = count($original_es_array);
	$cnt_expanded = count($expanded_es_array);

	if ( !$cnt_original ) $pass_es = false;
	if ( !$cnt_expanded ) $pass_es = false;
	if ( $cnt_original != $cnt_expanded ) $pass_es = false;

	if ( $pass_es ) {
		for ( $i = 0 ; $i < $cnt_original ; $i++ ) {
			if ( $original_es_array[$i] != $expanded_es_array[$i] ) $pass_es = false;
		}
	}

	$pass_ese = true;
	$pos_array = array_keys($used_word_list);
	$lpos = reset($pos_array);
	$rpos = end($pos_array);

	$ems_plus_pos_list = array();
	$ems_plus_lpos_list = array();
	$ems_plus_str_list = array();
	$plus_lpos = -1;
	for ( $i = $lpos ; $i <= $rpos ; $i++ ) {
		if ( $used_word_list[$i] ) {
			$plus_lpos = -1;
		} else if ( $coordinator_list[$i] ) {
			if ( $plus_lpos == -1 ) {
				$plus_lpos = $i;
				$ems_plus_lpos_list[$i] = true;
			}
			$ems_plus_pos_list[$i] = $plus_lpos;
			if ( $ems_plus_str_list[$plus_lpos] ) $ems_plus_str_list[$plus_lpos] .= " ";
			$ems_plus_str_list[$plus_lpos] .= $token_array[$i]['str'];
		} else {
			$pass_ese = false;
			break;
		}
	}
	
	$esem_lpos_list = array();
	foreach ( $plus_list as $pos => $val ) {
		if ( !isset($ems_plus_pos_list[$pos]) ) {
			$pass_ese = false;
			break;
		}
		$lpos = $ems_plus_pos_list[$pos];
		$esem_lpos_list[$lpos] = true;
	}
	if ( count($ems_plus_lpos_list) != count($esem_lpos_list) ) $pass_ese = false;
	foreach ( $ems_plus_lpos_list as $lpos => $val ) if ( !$esem_lpos_list[$lpos] ) $pass_ese = false;
	
	foreach ( $ems_plus_str_list as $lpos => $str ) {
		if ( !$allowed_coordinator[$str] ) $pass_ese = false;
	}

	return array('pass'=>$pass_es && $pass_ese, 'pass_es'=>$pass_es, 'pass_ese'=>$pass_ese);
}

function ems_expand_esem(&$model_array, &$idx, $depth)
{
	$plus_ast_array = array();
	$cnt_plus = 0;
	if ( $depth > 0 ) $idx++; // (
	while ( $idx < count($model_array) ) {
		$model = $model_array[$idx];
		if ( $model['type'] == 'operator' ) {
			if ( $model['value'] == '(' ) {
				$depth++;
				$plus_ast_array[$cnt_plus][] = ems_expand_esem($model_array, $idx, $depth); 
			} else if ( $model['value'] == ')' && $depth > 0 ) {
				break;
			} else if ( $model['value'] == '+' ) {
				$cnt_plus++;
			} else if ( $model['value'] == '*' ) {
				
			} 
		} else if ( $model['type'] == 'psu' ) {
			$plus_ast_array[$cnt_plus][] = array($model['value']); 
		}
		$idx++;
	}
	
	$plus_array = array();
	foreach ( $plus_ast_array as $ast_array ) {
		$sum_array = $ast_array[0];
		for ( $i = 1 ; $i < count($ast_array) ; $i++ ) {
			$sum_array = ems_expand_ast($sum_array, $ast_array[$i]);
		} 
		$plus_array = array_merge($plus_array, $sum_array);
	}
	return $plus_array;
}

function ems_expand_ast($arr1, $arr2)
{
	$plus_array = array();
	foreach ( $arr1 as $a1 ) {
		foreach ( $arr2 as $a2 ) {
			$plus_array[] = "{$a1}|{$a2}";
		}
	}
	return $plus_array;
}

function ems_make_matched_string(&$token_array, $matched_token_array)
{
	$matched_string = "";
	foreach ( $matched_token_array as $tpos ) {
		if ( $matched_string ) $matched_string .= " ";
		$matched_string .= "<span title='{$tpos}'>{$token_array[$tpos]['str']}</span>";
	}
	return $matched_string;
}

?>
